

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Iterative Deepening

The stack that is used in depth first search is implemented as a doubly linked list.



In [ ]:

    
from collections import deque

The function search takes three arguments to solve a search problem:

start is the start state of the search problem,
goalis the goal state, and
next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states. For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step. If successful, search returns a path from start to goal that is a solution of the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$

The procedure search tries to find a solution to the search problem by first trying to find a solution that has a length of $1$, then of length $2$, then of length $3$, etc. The search only stops when a solution is found.



In [ ]:

    
def search(start, goal, next_states):
    limit = 1
    while True:
        Path = depth_limited_search(start, goal, next_states, limit)
        if Path != None:
            return Path
        limit += 1

The function depth_limited_search tries to find a solution to the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle $$ that has a length of at most limit. The algorithm used is depth first search.



In [ ]:

    
def depth_limited_search(state, goal, next_states, limit):
    Stack = deque([[start]])
    while len(Stack) > 0:
        Path  = Stack.pop()
        state = Path[-1]
        if state == goal:
            return Path
        if len(Path) >= limit:  # A path that has a length of limit or more
            continue            # is discarded.
        for ns in next_states(state):
            if ns not in Path:
                Stack.append(Path + [ns])

Solving the Sliding Puzzle



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]: